/* Disjoint set data structure */
/* All in one file because it's so short */

#define FastAlg

#define NumSets 128

/* START: fig8_6.txt */
#ifndef _DisjSet_H

typedef int DisjSet[ NumSets + 1 ];
typedef int SetType;
typedef int ElementType;

void Initialize( DisjSet S );
void SetUnion( DisjSet S, SetType Root1, SetType Root2 );
SetType Find( ElementType X, DisjSet S );

#endif  /* _DisjSet_H */
/* END */

/* START: fig8_7.txt */
void
Initialize( DisjSet S )
{
    int i;

    for( i = NumSets; i > 0; i-- )
        S[ i ] = 0;
}
/* END */

#ifdef SlowAlg
/* START: fig8_8.txt */
/* Assumes Root1 and Root2 are roots */
/* union is a C keyword, so this routine */
/* is named SetUnion */

void
SetUnion( DisjSet S, SetType Root1, SetType Root2 )
{
    S[ Root2 ] = Root1;
}
/* END */

/* START: fig8_9.txt */
SetType
Find( ElementType X, DisjSet S )
{
    if( S[ X ] <= 0 )
        return X;
    else
        return Find( S[ X ], S );
}
/* END */
#else

/* START: fig8_13.txt */
/* Assume Root1 and Root2 are roots */
/* union is a C keyword, so this routine */
/* is named SetUnion */

void
SetUnion( DisjSet S, SetType Root1, SetType Root2 )
{
    if( S[ Root2 ] < S[ Root1 ] ) /* Root2 is deeper set */
        S[ Root1 ] = Root2;  /* Make Root2 new root */
    else
    {
        if( S[ Root1 ] == S[ Root2 ] )  /* Same height, */
            S[ Root1 ]--;               /* so update */
        S[ Root2 ] = Root1;
    }
}
/* END */

/* START: fig8_15.txt */
SetType
Find( ElementType X, DisjSet S )
{
    if( S[ X ] <= 0 )
        return X;
    else
        return S[ X ] = Find( S[ X ], S );
}
/* END */
#endif

main( )
{
    DisjSet S;
    int i, j, k, Set1, Set2;

    Initialize( S );
    j = k = 1;
    while( k <= 8 )
    {
        j = 1;
        while( j < NumSets )
        {
            Set1 = Find( j, S );
            Set2 = Find( j + k, S );
            SetUnion( S, Set1, Set2 );
            j += 2 * k;
        }
        k *= 2;
    }
    i = 1;
    for( i = 1; i <= NumSets; i++ )
    {
        Set1 = Find( i, S );
        printf( "%d**", Set1 );
    }
    printf( "\n" );
    return 0;
}

